This invention pertains to the encoding of video sequences for transmission over packet-switched networks (PSNs). In particular, it pertains to the compression and reconstruction of image signals using a new adaptive vector quantization (VQ) scheme suitable for packet video.
Vector quantization has been applied to speech coding for a number of years. However, the application of vector quantization to image coding is relatively new. Vector quantization has been applied both in the spatial and transformed domain in various forms. In its basic form, as illustrated in the block diagram of FIG. 1, an image is divided into blocks of N.times.N picture elements (pixels), reference number 31 in FIG. 3 In the transmitter and receiver identical code books 15 exist whose entries contain combinations of pixels in a block 31. Assuming that there are M shades of gray in an image, theoretically, (M).sup.N.times.N combinations are possible. In practice, however, there are only a limited number of combinations that occur most often, which reduces the size of the code table or code book considerably. The code book is created by training it over a large set of test images of different types. During the coding process, each block of the actual image 10, being compressed is compared 12 with entries 14 in the code book 15, and the address of that entry, which best matches, using the nearest neighbor rule, the image being compressed or encoded is transmitted 16 to the receiver. On the receive side, the received address is used to fetch 17 the same block 14 from the code book 15, which is then used to reconstruct the image 19. Typical block 14 and code book 15 sizes that are used are 4.times.4 and 256, respectively. Since it takes 8 bits to address an entry in the code book, a compression factor of 16 or bit rate of 0.5 bit per pixel is achieved, assuming that the original image is made up of 256 shades of gray. U.S. Pat. No. 4,797,739 issued to Tanaka is representative of the prior art.
Two major problems of vector quantization are: how to design a good code book that is representative of all the possible occurrences of pixel combinations in a block, and how to find a best match in the code book during the coding process. Some researchers have suggested various clustering techniques to design good code books. Tree searched algorithms have been used to speed up the code vector search process. A good overview of vector quantization can be found in Gray, IEEE ASSP Magazine, Apr. 1984, pp. 4-29. This invention does not relate to either the code table design or the search process. Rather, it deals with how to design an adaptive vector quantization which does not require sending of any side information, resulting in higher compression.
Most work in vector quantization has concentrated on compressing still-frame images. Application of vector quantization to color video compression is very recent. Broadcast video or image sequence compression poses a rather different set of requirements, in addition to those required for still-images. For example, video images may vary significantly from frame-to-frame and from scene-to-scene, and standard vector quantization code books may not be able to deliver a constant level of quality over a period of time. Furthermore, because of high pixel rate of video, the complexity and processing speed of a codec become important considerations in an algorithm. It is almost essential that an algorithm be adaptive to guarantee a level of performance over a wide range of types of video sequences. Two approaches which can be used to improve image quality are to increase the size of the fixed code book, or to keep the code book small but update the code book entries during the coding process. The first approach adversely affects the bit rate and the vector search time. In the latter approach to making vector quantization adaptive, the code book is updated either on a block-by-block basis or frame-by-frame basis, or at some other regular interval, to adapt to the local characteristics of a frame or sequence being coded. Work of some researchers in this area is based on the above approach. The major drawback of the approach adapted so far is that all the suggested techniques require sending either a new code book altogether every so often, or the new code words to replace the ones already in the code book, and this implies sending the side information. Although, the image quality improves, it is at the expense of increasing the bit rate. In summary, the code book size remains small and constant, but its entries are changed as a function of time.